<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en-us" lang="en-us">
<head>
  <link href="//gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta name="generator" content="Hugo 0.68.3" />

  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">

  <title>python数据结构----跳表 &middot; 我的博客</title>

  
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/print.css" media="print">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/poole.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/syntax.css">
  <link type="text/css" rel="stylesheet" href="/my_technology_blog/css/hyde.css">
    <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Abril+Fatface|PT+Sans:400,400i,700">


  
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/apple-touch-icon-144-precomposed.png">
  <link rel="shortcut icon" href="/favicon.png">

  
  
</head>

  <body class="theme-base-0b ">
  <aside class="sidebar">
  <div class="container sidebar-sticky">
    <div class="sidebar-about">
      <a href="/my_technology_blog/"><h1>我的博客</h1></a>
      <p class="lead">
       杨博的博客 
      </p>
    </div>

    <nav>
      <ul class="sidebar-nav">
        <li><a href="/my_technology_blog/">Home</a> </li>
        
      </ul>
    </nav>

    <p>&copy; 2021. All rights reserved. </p>
  </div>
</aside>

    <main class="content container">
    <div class="post">
  <h1>python数据结构----跳表</h1>
  <time datetime=2020-06-09T17:32:43&#43;0800 class="post-date">Tue, Jun 9, 2020</time>
  <h2 id="链表"><strong>链表</strong></h2>
<p>同数组比较，链表的插入删除操作复杂度是O(1)，然而如果想要查找一个节点，你可能会这么写：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">LinkedNode<span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>targetNode <span style="color:#f92672">=</span> headerNode;
<span style="color:#66d9ef">while</span>(targetNode)
{
	<span style="color:#66d9ef">if</span>(targetNode<span style="color:#f92672">-&gt;</span>element <span style="color:#f92672">==</span> theElement)
		<span style="color:#66d9ef">return</span> targetNode;
	targetNode <span style="color:#f92672">=</span> targetNode<span style="color:#f92672">-&gt;</span>next;
}
<span style="color:#66d9ef">return</span> NULL;
</code></pre></div><p>你会发现每次都是从链表头节点开始，时间复杂度是n（节点个数）。为了提高算法速度，就有了跳表的概念。</p>
<h2 id="跳表"><strong>跳表</strong></h2>
<p>结合链表和二分法的特点，将链表进行加工，创造一个二者的结合体：
1.链表从头节点到尾节点是有序的
2.可以进行跳跃查找（形如二分法）</p>
<p><strong>next数组</strong>
实现第一步，只需在插入的时候进行有序插入即可，核心步骤在第二步，构建一个可以实现在节点之间跳跃的链。
对于普通链表而言，你的节点也许会长这个样子（或者再多个构造析构函数？）:</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">T</span><span style="color:#f92672">&gt;</span>
<span style="color:#66d9ef">class</span> <span style="color:#a6e22e">linkedNode</span>
{
public:
	T element;
	linkedNode<span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>next;
};
</code></pre></div><p>这里的next指针是我们用于将此节点同后面一个节点连接的桥梁，正如你知道的那样，next是下一个节点的指针。</p>
<p>需要你考虑的事情来了，如果需要在不挨着的节点之间实现跳转，那么对于某一个节点来说，它就需要存储一个以上的指向别的节点的next指针。多个同种类型的数据通常可以采用数组存储（vector, list等STL容器也可以啦），这样，我们的跳表节点或许大概差不多应该长这个样子：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">T</span><span style="color:#f92672">&gt;</span>
<span style="color:#66d9ef">class</span> <span style="color:#a6e22e">skipNode</span>
{
public:
	T element;
	skipNode<span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;</span> <span style="color:#f92672">**</span>next; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">一个存储着</span>skipNode<span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;*</span><span style="color:#960050;background-color:#1e0010">类型变量的一维数组</span>
};
</code></pre></div><p>暂且不论next数组的大小是多少，先让我告诉你跳表的样子。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Ctiaobiao.png" alt=""></p>
<p>你可能会觉得跳表这个东西很奇怪，不过最好不是因为我画的比较丑。先不管竖着的线是什么，横着看每一层好像都是一个链表，对吗。另外我觉得你也应该注意一下竖着看的时候每一个节点的名字，它们也都是一样的（不用考虑为什么有的节点有一个，有的有两个甚至更多，这是插入函数应该解决的问题）。</p>
<p>所以我想你现在脑子中可能有了对next数组的一种假设，尽管事实可能并不是你想的那样，不过不要紧，让我借着这张图告诉你next数组是什么。</p>
<p>通常我们会定义跳表的级数，简单来解释，就是层数-1（最下面一级是0级）。所以这张图表示的跳表的级数是（0， 1， 2）。而在第2级的节点（比如node5)，它的next数组大小就是(2 + 1) == 3， 在第1级的节点（比如node4），它的next数组的大小就是（1 + 1） == 2， 在第0级的节点（比如node3），它的next数组大小是1；</p>
<p>所以在申请一个skipNode的指针时，传入这个节点所在的级数好像是理所应当的事情，然后对next进行初始化，把skipNode加工一下，像这样：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">T</span><span style="color:#f92672">&gt;</span>
<span style="color:#66d9ef">class</span> <span style="color:#a6e22e">skipNode</span><span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;</span>
{
public:
	skipNode(const T<span style="color:#f92672">&amp;</span> theElement, size_t size):
		element(theElement)
	{
		next <span style="color:#f92672">=</span> new skipNode<span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;*</span>[size<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>];
	}

	T element;
	skipNode<span style="color:#f92672">&lt;</span>T<span style="color:#f92672">&gt;</span> <span style="color:#f92672">**</span>next;
};
</code></pre></div><p>现在开始解释next数组，你最好看着上面的图：
对于第2级的node5来说</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">node5<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">2</span>] <span style="color:#f92672">==</span> tailNode;
node5<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">1</span>] <span style="color:#f92672">==</span> node7;
node5<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>] <span style="color:#f92672">==</span> node6;
</code></pre></div><p>对于第1级的node2来说</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">node2<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">1</span>] <span style="color:#f92672">==</span> node4;
node2<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>] <span style="color:#f92672">==</span> node3;
</code></pre></div><p><strong>find</strong>
这个函数可以帮助你更好地理解next数组的作用。</p>
<p><img src="C:%5Cwww%5Chugo_blog%5Cpublic%5Cimg%5Cfind.png" alt=""></p>
<p>继续看着这张图，让我先解释一下headerNode和tailNode是什么（如果你因为它们的存在感到一丝困惑的话），它们是设计者（就是我们啦）人为添加的两端节点，很像存在头节点和尾节点的链表（又或者像队列？），它们不存储需要保存的有用的数据，但是需要人为给定一个数，让它比整个跳表中的element都大，仅仅是用来判断是否是头和尾。当跳表为空时，级数为0，headerNode-&gt;next[0] == tailNode;</p>
<p>现在回到上面那个图片上，如果我想要查找node6，想想二分法（但不是从中间开始）。
假设targetNode记录着此时的节点，初值赋为headerNode；</p>
<p>第一次你应该比较的是headerNode-&gt;next[2]-&gt;element和theElement（待查找数据），也就是node5-&gt;element和theElement。显然node5小于theElement（别忘了跳表的数据也是有序的），**这一步的结果导致下一次应该从第2级的node5开始查询。**也就是令targetNode = targetNode-&gt;next[2];</p>
<p>第二次你应该比较targetNode-&gt;next[2]-&gt;element和theElement，也就是tailNode-&gt;element和theElement。看看前面，tailNode-&gt;element是最大的，对吗。所以结果是大于，**这一步的结果导致下一次应该从第1级的node5开始查询。**这里从第2级跳到第1级。但是没有改变targetNode。</p>
<p>第三次你应该比较targetNode-&gt;next[1]-&gt;element和theElement，也就是node7-&gt;element和theElement。显然也是大于，**这一步的结果导致下一次应该从第0级的node5开始查询。**这里从第1级跳到第0级。也没有改变targetNode。</p>
<p>第四次你应该比较targetNode-&gt;next[0]-&gt;element和theElement，也就是node6-&gt;element和theElement。这时你应该庆幸终于相等了，此时结束。如果小于，改变targetNode = targetNode-&gt;next[0]（像第一步那样），如果大于，结束，不然还往哪一级降，没了，对吗。</p>
<p>没懂？接着看：
比较的时候的三种情况，以targetNode-&gt;next[i]-&gt;element和theElement为例：
1.小于：令targetNode = targetNode-&gt;next[i]; //第i级链表的下一个
2.大于：向下降级，i- - //不改变targetNode
3.等于：向下降级，i- - //不改变targetNode</p>
<p>退出后，再次比较targetNode-&gt;next[0]和theElement，判断是否找到。
所以整个运算下来，targetNode是要查找的节点前面那个节点。如果你不明白，想想找不到那个节点时的情况，比如说，额，查找node6.6。
让我们看看代码：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">K</span>, <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">E</span><span style="color:#f92672">&gt;</span>
pair<span style="color:#f92672">&lt;</span>const K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>::find(const K<span style="color:#f92672">&amp;</span> theKey)
{
	skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;*</span> beforeNode <span style="color:#f92672">=</span> headerNode;
	<span style="color:#66d9ef">for</span>(int i <span style="color:#f92672">=</span> curLevels; i <span style="color:#f92672">&gt;=</span> <span style="color:#ae81ff">0</span>; <span style="color:#f92672">--</span>i) <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">降级</span>
	{
		<span style="color:#66d9ef">while</span>(beforeNode<span style="color:#f92672">-&gt;</span>next[i]<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">&lt;</span> theKey)
			beforeNode <span style="color:#f92672">=</span> beforeNode<span style="color:#f92672">-&gt;</span>next[i]; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">跳转到同一级的下一个</span>
	}
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">跳出存在两种可能</span>
	<span style="color:#f92672">//</span><span style="color:#ae81ff">1.</span><span style="color:#960050;background-color:#1e0010">找到了，此时</span> <span style="color:#66d9ef">if</span>(beforeNode<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">==</span> theKey)
	<span style="color:#f92672">//</span><span style="color:#ae81ff">2.</span><span style="color:#960050;background-color:#1e0010">没找到，此时</span> <span style="color:#66d9ef">if</span>(beforeNode<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">&gt;</span> theKey)
	<span style="color:#66d9ef">if</span>(beforeNode<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">==</span> theElement<span style="color:#f92672">.</span>first)
		<span style="color:#66d9ef">return</span> <span style="color:#f92672">&amp;</span>beforeNode<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>]<span style="color:#f92672">-&gt;</span>element;
	<span style="color:#66d9ef">return</span> NULL;
}
</code></pre></div><p><strong>insert</strong>
像红黑树，AVL树一样，跳表也是一种平衡结构，只不过这种平衡结构是利用随机函数产生的级数维持的（终于填了前面的坑，还记得吗，为什么有的节点有2级，有的只有0级）。</p>
<p>接着上面那个图，想想插入node6.6的过程中会发生什么（假设随机函数给它分配的是第2级）。。。静思一秒钟。
啊！插入之后会破坏每一级的结构，会破坏哪些节点的结构呢。。。静思一秒钟。
啊！自然是第2级的node5，第1级的node5，第0级的node6这些节点的next数组。</p>
<p>分析过后，第一步便是找到这几个节点。我觉得你应该停一下想想怎么找，实在想不出来，参考find函数。
find函数中，for循环内套while循环，想想每次while循环结束之后的beforeNode是什么。哇哦，它就是我们要找的节点。我们用一个last数组记录这些节点，last[i]表示第i级要找的节点。</p>
<p>第二步：利用随机函数分配级数level
找节点是为了改变这些节点的next数组，分配级数是为了只改变找到的那些节点中位于第0级到第level级的节点。啊！你又想了，万一随机出的level比目前最大级数还大怎么办。这时就将跳表增加一级呗，像这样：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">int level <span style="color:#f92672">=</span> levels();
<span style="color:#66d9ef">if</span>(level <span style="color:#f92672">&gt;</span> curLevels)
{
	level <span style="color:#f92672">=</span> <span style="color:#f92672">++</span>curLevels;
	last<span style="color:#f92672">-&gt;</span>next[level] <span style="color:#f92672">=</span> heaerNode; 
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">增加一级的同时也要改变</span>last数组
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">用于将新节点插入时</span>newNode<span style="color:#f92672">-&gt;</span>next[level] <span style="color:#f92672">=</span> last[level]<span style="color:#f92672">-&gt;</span>next[level]
}
</code></pre></div><p>万事俱备后，开始更新涉及到的节点的next数组，看代码之前，先想想怎么在链表中插入节点。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">skipNode<span style="color:#f92672">&lt;</span>K,E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>newNode <span style="color:#f92672">=</span> new skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>(thePair, level<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>);

<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">因为只影响了</span>[<span style="color:#ae81ff">0</span>, level]<span style="color:#960050;background-color:#1e0010">级的节点，更高级的节点不受影响</span>
<span style="color:#66d9ef">for</span>(int i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;=</span> level; <span style="color:#f92672">++</span>i)
{
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">每一级都插入新节点</span>
	newNode<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">=</span> last[i]<span style="color:#f92672">-&gt;</span>next[i];
	last[i]<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">=</span> newNode;
}
</code></pre></div><p>总结一下插入函数，需要两个额外的函数：
1.随机函数，用于生成新节点的级数
2.初始化last数组，保存每一级中处在待插入位置前面的节点</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">随机函数，为新节点生成级数</span>
template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">K</span>, <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">E</span><span style="color:#f92672">&gt;</span>
int skipList<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>::levels()
{
	int level <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>;
	<span style="color:#f92672">//</span>cutOff预先设定的值,cutOff <span style="color:#f92672">=</span> prob <span style="color:#f92672">*</span> MAX_RAND;
	<span style="color:#f92672">//</span>prob:<span style="color:#960050;background-color:#1e0010">是第</span>i级同时又是第i<span style="color:#f92672">-</span><span style="color:#ae81ff">1</span><span style="color:#960050;background-color:#1e0010">级的概率，人为设定</span>
	<span style="color:#66d9ef">while</span>(rand() <span style="color:#f92672">&gt;</span> cutOff) 
		level<span style="color:#f92672">++</span>;
	<span style="color:#66d9ef">return</span> level;
}


template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">K</span>, <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">E</span><span style="color:#f92672">&gt;</span>
skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;*</span> skipList<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>::search(const K<span style="color:#f92672">&amp;</span> theKey)
{
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">与</span>find函数相同
	skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;*</span> beforeNode <span style="color:#f92672">=</span> headerNode;
	<span style="color:#66d9ef">for</span>(int i <span style="color:#f92672">=</span> curLevels; i <span style="color:#f92672">&gt;=</span> <span style="color:#ae81ff">0</span>; <span style="color:#f92672">--</span>i)
	{
		<span style="color:#66d9ef">while</span>(beforeNode<span style="color:#f92672">-&gt;</span>next[i]<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">&lt;</span> theKey)
			beforeNode <span style="color:#f92672">=</span> beforeNode<span style="color:#f92672">-&gt;</span>next[i];
		last[i] <span style="color:#f92672">=</span> beforeNode; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">找到每一级待插入位置前面的节点</span>
	}
	
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">返回找到的节点，用于判断是否已存在键为</span>theKey的节点
	<span style="color:#66d9ef">return</span> beforeNode<span style="color:#f92672">-&gt;</span>next[<span style="color:#ae81ff">0</span>];
}


template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">K</span>, <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">E</span><span style="color:#f92672">&gt;</span>
void skipList<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>::insert(const pair<span style="color:#f92672">&lt;</span>const K, E<span style="color:#f92672">&gt;&amp;</span> thePair)
{
	<span style="color:#66d9ef">if</span>(thePair<span style="color:#f92672">.</span>first <span style="color:#f92672">&gt;=</span> tailNode<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first)
		<span style="color:#66d9ef">return</span>;

	skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>theNode <span style="color:#f92672">=</span> search(thePair<span style="color:#f92672">.</span>first);
	<span style="color:#66d9ef">if</span>(theNode<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">==</span> thePair<span style="color:#f92672">.</span>first) <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">判断是否存在该节点</span>
	{
		theNode<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>second <span style="color:#f92672">=</span> thePair<span style="color:#f92672">.</span>second; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">更新值</span>
		<span style="color:#66d9ef">return</span>;
	}

	int level <span style="color:#f92672">=</span> levels();
	<span style="color:#f92672">//</span>cutLevels<span style="color:#960050;background-color:#1e0010">：记录当前最大级数</span>
	<span style="color:#66d9ef">if</span>(level <span style="color:#f92672">&gt;</span> curLevels)
	{
		level <span style="color:#f92672">=</span> <span style="color:#f92672">++</span>curLevels; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">级数加一</span>,<span style="color:#960050;background-color:#1e0010">让新节点作为最高级节点</span>
		last[level] <span style="color:#f92672">=</span> headerNode;
	}
	
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">每一级如同链表插入一样进行插入</span>
	skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>newNode <span style="color:#f92672">=</span> new skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>(thePair, level<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>);
	<span style="color:#66d9ef">for</span>(int i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;=</span> level; <span style="color:#f92672">++</span>i)
	{
		newNode<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">=</span> last[i]<span style="color:#f92672">-&gt;</span>next[i];
		last[i]<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">=</span> newNode;
	}
	dSize<span style="color:#f92672">++</span>;
}
</code></pre></div><p><strong>erase</strong>
如果你理解了插入函数，删除函数会带给你从未有过的轻松感，至少比起还在文章开头徘徊的你是这样。噢对，还有一件事，或许你应该在回忆链表删除的状态里待几秒钟。如果没有头绪，插入函数最后一个for循环说不定会帮到你。</p>
<p>要删除一个节点，自然是先找到这个节点啦，同时还要初始化last数组啦。然后从第0级开始到最高级，如果last[i]-&gt;next[i]是要删除的节点，就删除掉。直接上代码：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">K</span>, <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">E</span><span style="color:#f92672">&gt;</span>
void skipList<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>::erase(const K<span style="color:#f92672">&amp;</span> theKey)
{
	<span style="color:#66d9ef">if</span>(theKey <span style="color:#f92672">&gt;=</span> tailNode<span style="color:#f92672">-&gt;</span>first)
		<span style="color:#66d9ef">return</span>;

	skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>theNode <span style="color:#f92672">=</span> search(theKey);
	<span style="color:#66d9ef">if</span>(theNode<span style="color:#f92672">-&gt;</span>element<span style="color:#f92672">.</span>first <span style="color:#f92672">!=</span> theKey)
		<span style="color:#66d9ef">return</span>; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">不存在要删除的节点</span>

	int i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>;
	<span style="color:#66d9ef">while</span>(i <span style="color:#f92672">&lt;=</span> curLevels <span style="color:#f92672">&amp;&amp;</span> last[i]<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">==</span> theNode)
	{
		<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">每一级的链表删除</span>
		last[i]<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">=</span> theNode<span style="color:#f92672">-&gt;</span>next[i];
		i<span style="color:#f92672">++</span>;
	}
	
	<span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">如果删除的是最高级，且未删除前，最高级就一个节点，则当前节点减一</span>
	<span style="color:#66d9ef">while</span>(curLevles <span style="color:#f92672">&gt;</span> <span style="color:#ae81ff">0</span> <span style="color:#f92672">&amp;&amp;</span> headerNode<span style="color:#f92672">-&gt;</span>next[curLevels] <span style="color:#f92672">==</span> tailNode)
		curLevels<span style="color:#f92672">--</span>;

	delete theNode;
	dSize<span style="color:#f92672">--</span>;
}
</code></pre></div><p>现在唯一可能会让你感到头疼的就是构造函数了。想想构造函数应该做些什么，对数据成员进行初始化？啊，对，那是所有构造函数应该做的事情。我说的是具体应该怎么做。</p>
<p>我猜你看上述代码的时候会对像cutOff, curLevels这些凭空出现的变量有点不理解，没关系，正如你想的那样，把它们放到private数据成员里。总结一下让你感到困惑的变量：</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python">int dSize; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">记录着跳表中节点的个数，初始为</span><span style="color:#ae81ff">0</span>
int curLevels; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">记录跳表当前最大级数，如果是图片那样的话，它的值是</span><span style="color:#ae81ff">2</span>
int cutOff; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">用于随机函数的随机算法，一个很大的值</span>
int maxLevel; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">跳表可以存储的最大级数</span>
skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>heaerNode; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">跳表头节点，键是跳表中最大的</span>
skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">*</span>tailNode; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">尾节点，键同</span>headerNode
skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> <span style="color:#f92672">**</span>last; <span style="color:#f92672">//</span><span style="color:#960050;background-color:#1e0010">记录每一级中要查找的节点前面那个节点</span>
</code></pre></div><p>构造函数首先初始化这些变量，然后给节点申请内存，将头节点和尾节点连接起来（因为此时跳表是空的）。就这么简单。</p>
<div class="highlight"><pre style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-python" data-lang="python"><span style="color:#f92672">//</span>prob: <span style="color:#960050;background-color:#1e0010">是第</span>i级同时又是第i<span style="color:#f92672">-</span><span style="color:#ae81ff">1</span><span style="color:#960050;background-color:#1e0010">级的概率</span>
<span style="color:#f92672">//</span>maxPairs: <span style="color:#960050;background-color:#1e0010">跳表可以存储的最多节点个数</span>
<span style="color:#f92672">//</span>largetKey: <span style="color:#960050;background-color:#1e0010">最大键</span>
template<span style="color:#f92672">&lt;</span><span style="color:#66d9ef">class</span> <span style="color:#a6e22e">K</span>, <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">E</span><span style="color:#f92672">&gt;</span>
skipList<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>::skipList(K largerKey, int maxPairs, double prob):
	cutOff(prob <span style="color:#f92672">*</span> RAND_MAX),
	maxLevel((int)ceil(logf((float)maxPairs) <span style="color:#f92672">/</span> logf(<span style="color:#ae81ff">1</span> <span style="color:#f92672">/</span> prob)) <span style="color:#f92672">-</span> <span style="color:#ae81ff">1</span>),
	cutLevels(<span style="color:#ae81ff">0</span>),
	dSize(<span style="color:#ae81ff">0</span>)
{
	pair<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span> tailPair;
	tailPair<span style="color:#f92672">.</span>first <span style="color:#f92672">=</span> largerKey;
	headerNode <span style="color:#f92672">=</span> new skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>(tailPair, maxLevel<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>);
	tailNode <span style="color:#f92672">=</span> new skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;</span>(tailPair, <span style="color:#ae81ff">0</span>);
	last <span style="color:#f92672">=</span> new skipNode<span style="color:#f92672">&lt;</span>K, E<span style="color:#f92672">&gt;*</span>[maxLevel<span style="color:#f92672">+</span><span style="color:#ae81ff">1</span>];

	<span style="color:#66d9ef">for</span>(int i <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; i <span style="color:#f92672">&lt;=</span> maxLevel; <span style="color:#f92672">++</span>i)
	{
		headerNode<span style="color:#f92672">-&gt;</span>next[i] <span style="color:#f92672">=</span> tailNode; 
	}
}
</code></pre></div><p>对第0级的每一个节点，释放它的next数组（可以写在skipNode的析构函数中），然后释放它自己。</p>

</div>


    </main>

    
  </body>
</html>
